package com.wushijia.datastructure;

/**
 * 跳表是在单链表的基础上加入索引，使查找效率大大提高的一种各方面性能都很优秀的数据结构 跳表存储正整数，且不重复
 *
 * @author hzk
 */
public class MySkipList {

  private final int MAX_LEVEL = 16;//最大索引层数（0~原链表 15~最高一级索引）
  private int levelCount = 1;//跳表当前索引层数
  public Node head = new Node();//跳表头

  /**
   * 查找跳表中值为value的节点
   *
   * @param value 要查找的值
   * @return 找到返回对应节点，否则返回null
   */
  public Node find(int value) {
    Node p = head;
    //找到该层索引中小于value的最大节点
    for (int i = levelCount - 1; i >= 0; i--) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  /**
   * 将value插入跳表中
   *
   * @param value 待加入数据
   */
  public void insert(int value) {
    int level = randomLevel();
    if (levelCount < level) {
      levelCount = level;
    }

    Node p = head;
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;

    Node path[] = new Node[level];//存储查找value时经过各层的索引
    for (int i = level - 1; i >= 0; i--) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      path[i] = p;
    }

    //将value插入各层索引中
    for (int i = level - 1; i >= 0; i--) {
      newNode.forwards[i] = path[i].forwards[i];
      path[i].forwards[i] = newNode;
    }
  }

  /**
   * insert的优化版本，去掉了path[]
   *
   * @param value 待加入数据
   */
  public void insert_optimized(int value) {
    int level = randomLevel();
    if (levelCount < level) {
      levelCount = level;
    }

    Node p = head;
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;

    for (int i = level - 1; i >= 0; i--) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }

      //这层索引是最后一个则直接插入
      if (p.forwards[i] == null) {
        p.forwards[i] = newNode;
      }
      //否则插在中间
      else {
        newNode.forwards[i] = p.forwards[i];
        p.forwards[i] = newNode;
      }
    }
  }

  /**
   * 删除跳表中值为value的节点及索引
   *
   * @param value 待删除结点的值
   */
  public void delete(int value) {
    Node[] path = new Node[levelCount];
    Node p = head;

    for (int i = levelCount - 1; i >= 0; i--) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      path[i] = p;
    }

    //找到
    if (p.forwards[0] != null && p.forwards[0].data == value) {
      //删除节点所有索引
      for (int i = levelCount - 1; i >= 0; i--) {
        if (p.forwards[i] != null && p.forwards[i].data == value) {
          p.forwards[i] = p.forwards[i].forwards[i];
        }
      }
    }
  }

  /**
   * 随机生成索引层数，索引层数和生成概率负相关 尽量使一级索引占全部索引的50%，二级索引占25%，三级索引占12.5%…… 随机函数能防止链表数据全部集中在某两个索引之间
   *
   * @return
   */
  private int randomLevel() {
    int level = 1;

    while (Math.random() < 0.5 && level < MAX_LEVEL) {
      level++;
    }

    return level;
  }

  public void printAll() {
    Node p = head;
    while (p.forwards[0] != null) {
      System.out.print(p.forwards[0].data + " ");
      p = p.forwards[0];
    }
    System.out.println();
  }

  public static void skipListText() {
    MySkipList list = new MySkipList();
    list.insert(1);
    list.insert(2);
    list.insert(3);
    list.printAll();
    System.out.println(list.find(2));
    list.delete(2);
    list.printAll();
    list.insert_optimized(2);
    list.printAll();
  }

  public class Node {

    private int data = -1;//节点数据
    private Node forwards[] = new Node[MAX_LEVEL];//存储节点上层索引
    private int maxLevel = 0;//最大索引层数

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();

      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");

      return builder.toString();
    }
  }
}
